COMMENT ⊗   VALID 00007 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Exercise - Dynamic Programming
C00006 00003	Exercise
C00007 00004	Write a program to pretend to be a therapist, reading sentences in English from
C00008 00005
C00011 00006	A convex polygon of  N sides can be cut into N-2 triangles in a number of ways,
C00012 00007	Exercise, dynamic programming.
C00013 ENDMK
C⊗;
Exercise - Dynamic Programming

Some positions that arise in the game of backgammon become simple races,
where the first player to roll a large enough cumulative total on the dice
wins the game.  A player rolls two dice; if the numbers on the dice are
different, the player gets the sum, but if the numbers are equal, he gets
twice the sum; 1 & 2 gives the player 3, while 6 & 6 gives him 24.  

Calculate the average number of turns required for a player to accumulate a
total of 100.  Warning: don't fall into the trap of dividing 100 by the
average roll (8 1/6).

Harder Exercise - Dynamic Programming

Calculate the winning chance of the player whose turn is next in a
backgammon race (see previous problem), if the first player needs a total
of 38, and the second a total of 40.

Hardest Exercise - Dynamic Programming (Suitable for term project)

In backgammon as played for money, at any one time one (or initially both)
of the players has the right to double the stakes before rolling the dice,
if he thinks that on the average he will win the most money by doing so. 
The opponent may either give up the game, paying the current stake, or
agree to let the game continue for twice the current stake, in which case
the first player proceeds with his dice roll.  When a player uses the right
to double, he loses it and the other player gets it, so doubling alternates
between the players.

In the situation of the previous problem, if the first player has doubled
earlier in the game, so that the current stake is 2 units,  on the average
what will be the first player's net winnings, counting losses as negative
winnings?  Assume that each player offers and accepts doubles to maximize
average net winnings.  To make the problem harder, assume that neither
player has doubled; find the first player's average winnings, and determine
whether he should double before his first roll of the dice.
Exercise

Given a two-dimensional grid, as shown below, using array coordinates, and given
the real coordinate pairs (A1,B1) and A2,B2) of two points P1 and P2 in the region,
we want to record in an array the set of squares through which the straight line
segments from P1 and P2 passes.

Write a program to pretend to be a therapist, reading sentences in English from
the terminal. If an input sentence contains "am", the program should respond by
a confirmation, changing "am" to "are", "I" to "you", etc.:

Input: I am angry.
Output: You say you are angry.

It should respond to sentences containing family names, like "brother", with
"Tell me more about your family."

It should respond to "I don't like (trust, etc.) you" with "I'm only trying to
help you." If al else fails, it should say "Yes," or "Go on," or the like.



The input:				The desired character array.
A1=1.3, B1=2.5,				Image[2,3]=`*'
A2=5.4, B2=6.6				Image[2,4]=`*', etc.

A procedure to do this task can be used in a program to print crude line
drawings using a standard line (character) printer or a character-based
terminal screen.

The line through P1 and P2 passes through a particular square if it goes above
at least one of the four corners, and below at least one.
























As the illustration above shows, when B1<B2, the point (A,B) falls 
above the line if A>A1+(B-B1)(A2-A1)/(B2-B1), and below the line if 
A<A1+(B-B1)(A2-A1)/(B2-B1).

Here is a proposed Pascal program to put the line segment into a page image
and print it.

(Declarations)

PROCEDURE ABOVE(VERT,HORIZ:REAL):BOOLEAN;
	BEGIN
	ABOVE:=VERT>A1+(HORIZ-B1)*(A2-A1)/(B2-B1)
	END;

PROCEDURE BELOW(VERT,HORIZ:REAL):BOOLEAN;
	BEGIN
	BELOW:=VERT<A1+(HORIZ-B1)*(A2-A1)/(B2-B1)
	END;

READ(A1,B1,A2,B2);
FOR R:=1 TO 132 DO
	FOR C:=1 TO 60 DO
		IF (ABOVE(R-1,C-1) OR ABOVE(R-1,C))
			AND (BELOW(R,C-1) OR BELOW(R,C))
		THEN IMAGE[R,C]:=`*'
		ELSE IMAGE[R,C]:=` ';
WRITEPAGE(IMAGE) 


Unfortunately, the program is incorrect, in at least two ways.  It fails if

	A1= 5, B1=17, A2= 5, B2=43, and also if
   	A1=17, B1= 5, A2=43, B2= 5.

Your task: find all errors and report them. Correct them.  Test the corrected
program, and submit with it, in legible and coherent English, a persuasive
argument that it now works on any values of A1,B1,A2,B2.

A convex polygon of  N sides can be cut into N-2 triangles in a number of ways,
as shown below:

















Design a program which, given the coordinates of the vertices, finds the
triangulation that minimizes the total length of the cuts.
Exercise, dynamic programming.























Any convex polygon can be divided into triangles, as shown above, usually in
many ways.  Given the coordinates of the vertices, find the triangulation that
uses the least ink.